{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pairs of Songs With Total Durations Divisible by 60"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numPairsDivisibleBy60"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #总持续时间可被 60 整除的歌曲"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在歌曲列表中，第 <code>i</code> 首歌曲的持续时间为 <code>time[i]</code> 秒。</p>\n",
    "\n",
    "<p>返回其总持续时间（以秒为单位）可被 <code>60</code> 整除的歌曲对的数量。形式上，我们希望下标数字 <code>i</code> 和 <code>j</code> 满足&nbsp; <code>i &lt; j</code> 且有&nbsp;<code>(time[i] + time[j]) % 60 == 0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>time = [30,20,150,100,40]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>这三对的总持续时间可被 60 整除：\n",
    "(time[0] = 30, time[2] = 150): 总持续时间 180\n",
    "(time[1] = 20, time[3] = 100): 总持续时间 120\n",
    "(time[1] = 20, time[4] = 40): 总持续时间 60\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>time = [60,60,60]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>所有三对的总持续时间都是 120，可以被 60 整除。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= time.length &lt;= 6 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= time[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pairs-of-songs-with-total-durations-divisible-by-60](https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pairs-of-songs-with-total-durations-divisible-by-60](https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[30,20,150,100,40]', '[60,60,60]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        mod_time: List[int] = [0] * 60\n",
    "\n",
    "        for t in time:\n",
    "            mod_time[t % 60] += 1\n",
    "\n",
    "        ans: int = 0\n",
    "        if mod_time[0] > 1:\n",
    "            ans += (mod_time[0] * (mod_time[0] - 1)) // 2\n",
    "        if mod_time[30] > 1:\n",
    "            ans += (mod_time[30] * (mod_time[30] - 1)) // 2\n",
    "\n",
    "        i, j = 1, 59\n",
    "        while i < j:\n",
    "            ans += mod_time[i] * mod_time[j]\n",
    "            i, j = i + 1, j - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(time)):\n",
    "            time[i] %= 60\n",
    "            d[time[i]] = d.get(time[i], 0) + 1\n",
    "        count = 0\n",
    "        for k,v in d.items():\n",
    "            if k in (0, 30):\n",
    "                count += v * (v - 1) // 2\n",
    "            elif k < 30:\n",
    "                count += v * d.get(60 - k, 0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        d = {}\n",
    "        for x in time:\n",
    "            x %= 60\n",
    "            d[x] = d.get(x, 0) + 1\n",
    "        count = 0\n",
    "        for k,v in d.items():\n",
    "            if k in (0, 30):\n",
    "                count += v * (v - 1) // 2\n",
    "            elif k < 30:\n",
    "                count += v * d.get(60 - k, 0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        res = 0\n",
    "        dp = [0]*60\n",
    "        for item in time:\n",
    "            k = item%60\n",
    "            res += dp[0 if k==0 else 60-k]\n",
    "            dp[k]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        time = [d % 60 for d in time]\n",
    "        \n",
    "        res = 0\n",
    "        defaultDict = {}\n",
    "        for t in time:\n",
    "            dt = (60 - t) % 60\n",
    "            if dt in defaultDict:\n",
    "                res += defaultDict[dt]\n",
    "            \n",
    "            defaultDict[t] = defaultDict.get(t,0) + 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        length: int = len(time)\n",
    "        result: int = 0\n",
    "        count0: int = 0\n",
    "        for i in range(0, length):\n",
    "            time[i] = time[i] % 60\n",
    "            if time[i] == 0:\n",
    "                count0 += 1\n",
    "        time.sort()\n",
    "        # print(time)\n",
    "        i: int = 0\n",
    "        j: int = length - 1\n",
    "        while i < j:\n",
    "            if time[i] + time[j] == 60:\n",
    "                result += 1\n",
    "                oldi = i\n",
    "                oldj = j\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                while (time[i] == time[i - 1] and i < oldj):\n",
    "                    result += 1\n",
    "                    i += 1\n",
    "                while (time[j] == time[j + 1] and oldi < j):\n",
    "                    result += 1\n",
    "                    j -= 1\n",
    "                i = oldi + 1\n",
    "                j = oldj - 1\n",
    "            elif time[i] + time[j] < 60:\n",
    "                i += 1\n",
    "            elif time[i] + time[j] > 60:\n",
    "                j -= 1\n",
    "        result += count0 * (count0 - 1) // 2\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        length: int = len(time)\n",
    "        result: int = 0\n",
    "        count0: int = 0\n",
    "        for i in range(0, length):\n",
    "            time[i] = time[i] % 60\n",
    "            if time[i] == 0:\n",
    "                count0 += 1\n",
    "        time.sort()\n",
    "        # print(time)\n",
    "        i: int = 0\n",
    "        j: int = length - 1\n",
    "        while i < j:\n",
    "            if time[i] + time[j] == 60:\n",
    "                result += 1\n",
    "                oldi = i\n",
    "                oldj = j\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                while (time[i] == time[i - 1] and i < oldj):\n",
    "                    result += 1\n",
    "                    i += 1\n",
    "                while (time[j] == time[j + 1] and oldi < j):\n",
    "                    result += 1\n",
    "                    j -= 1\n",
    "                i = oldi + 1\n",
    "                j = oldj - 1\n",
    "            elif time[i] + time[j] < 60:\n",
    "                i += 1\n",
    "            elif time[i] + time[j] > 60:\n",
    "                j -= 1\n",
    "        result += count0 * (count0 - 1) // 2\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        count = [0]*60\n",
    "        sumCnt = 0\n",
    "        for t in time:\n",
    "            if t%60==0:    \n",
    "                sumCnt += count[0]\n",
    "            else:\n",
    "                sumCnt += count[60-t%60]\n",
    "            count[t%60] += 1\n",
    "        return sumCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        dic = collections.Counter()\n",
    "        for t in time:\n",
    "            dic[t%60] +=1\n",
    "        res = 0\n",
    "        for i in range(1, 30):\n",
    "            res += dic[i]*dic[60-i]\n",
    "        res += (dic[0]-1)*dic[0]//2\n",
    "        res += (dic[30]-1)*dic[30]//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        temp = {}\n",
    "        for i in range(len(time)):\n",
    "            time[i] = time[i] % 60\n",
    "            if time[i] not in temp:\n",
    "                temp[time[i]] = 1\n",
    "            else:\n",
    "                temp[time[i]] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        print(temp)\n",
    "        for i, j in temp.items():\n",
    "            if i == 0:\n",
    "                ans += (j * (j - 1))\n",
    "            elif(i == 30 and j >= 2):\n",
    "                ans += (j * (j - 1))\n",
    "            elif 60 - i in temp:\n",
    "                ans += (j * temp[60 - i])\n",
    "            print(ans)\n",
    "        return int(ans / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        N=len(time)\n",
    "        for i in range(N):\n",
    "            time[i]%=60\n",
    "        dic={}\n",
    "        \n",
    "        ans=0\n",
    "        for i in time:\n",
    "            if 60-i in dic:\n",
    "                ans+=dic[60-i]\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "                if i==0:\n",
    "                    dic[60]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "                if i==0:\n",
    "                    dic[60]+=1\n",
    "            \n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        count = defaultdict(int)\n",
    "        ans = 0\n",
    "        for i in range(len(time)):\n",
    "            time[i] = time[i] % 60\n",
    "        for j in time:\n",
    "            cur = (60 - j) % 60\n",
    "            ans += count[cur]\n",
    "            count[j] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        le=len(time)\n",
    "        count=0\n",
    "        for n in range(le):\n",
    "            time[n]=time[n]%60\n",
    "        from collections import Counter\n",
    "        Time=dict(Counter(time))\n",
    "        if 0 in Time.keys():\n",
    "            for n in range(Time[0]):\n",
    "                count+=n\n",
    "            del Time[0]\n",
    "        if 30 in Time.keys():\n",
    "            for n in range(Time[30]):\n",
    "                count+=n\n",
    "            del Time[30]\n",
    "        small=dict()\n",
    "        big=dict()\n",
    "        for i in Time.keys():\n",
    "            if i <30:\n",
    "                small[i]=Time[i]\n",
    "            else:\n",
    "                big[i]=Time[i]\n",
    "        for i in small.keys():\n",
    "            for j in big.keys():\n",
    "                if i+j==60:\n",
    "                    count+=small[i]*big[j]\n",
    "                    big.pop(j)\n",
    "                    break\n",
    "            if not big:\n",
    "                break\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        le=len(time)\n",
    "        count=0\n",
    "        for n in range(le):\n",
    "            time[n]=time[n]%60\n",
    "        yu=[0]*60\n",
    "        for i in time:\n",
    "            yu[i]+=1\n",
    "        if yu[0]:\n",
    "            for n in range(yu[0]):\n",
    "                count+=n\n",
    "        if yu[30]:\n",
    "            for n in range(yu[30]):\n",
    "                count+=n\n",
    "            yu[30]=0\n",
    "        i=1\n",
    "        j=59\n",
    "        while i<j:\n",
    "            count+=yu[i]*yu[j]\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        \n",
    "        d = collections.defaultdict(int)\n",
    "        for i in range(len(time)):\n",
    "            time[i] %= 60\n",
    "            d[time[i]] += 1\n",
    "\n",
    "        ans: int = 0\n",
    "        \n",
    "        if 0 in d:\n",
    "            ans =  ans + d[0] * (d[0]-1) // 2\n",
    "\n",
    "        if 30 in d:\n",
    "            ans =  ans + d[30] * (d[30]-1) // 2\n",
    "\n",
    "        i: int = 1\n",
    "        j: int = 59\n",
    "        while i < j:\n",
    "            if i in d and j in d:\n",
    "                ans += d[i] * d[j]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        h = collections.defaultdict(int)\n",
    "        dui = 0\n",
    "        for i in time:\n",
    "            if (i%60) in h:\n",
    "                dui = dui + h[i%60]\n",
    "            if (i%60) == 0:\n",
    "                h[0] += 1\n",
    "\n",
    "            else:\n",
    "                h[60 - (i%60)] += 1\n",
    "            \n",
    "        return dui"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        def factorial_(n):\n",
    "            result=1\n",
    "            for i in range(2,n+1):\n",
    "                result=result*i\n",
    "            return result\n",
    "\n",
    "        def comb_2(n,m):\n",
    "            return factorial_(n)//(factorial_(n-m)*factorial_(m))              #使用自己的阶乘函数计算组合数\n",
    "\n",
    "        count = 0\n",
    "        L = len(time)\n",
    "        for i in range(L):\n",
    "            time[i] = time[i] % 60\n",
    "        d = {}\n",
    "\n",
    "        for i in time:\n",
    "            if i in d:\n",
    "                d[i] += 1\n",
    "            else:\n",
    "                d[i] = 1\n",
    "        # print(d)\n",
    "\n",
    "        for i in d:\n",
    "            # print(i, d[i] ,count)\n",
    "            if d[i] == -1:\n",
    "                continue\n",
    "            if i == 30 or i == 0:\n",
    "                # print('----', len(list(itertools.combinations('A' * d[i], 2))))\n",
    "                count += (comb_2(d[i],2))\n",
    "                d[i] = -1\n",
    "            else:\n",
    "                t = (60 - i)\n",
    "                if t not in d:\n",
    "                    continue\n",
    "                if d[t] == -1:\n",
    "                    continue\n",
    "                count += d[i] * d[t]\n",
    "                d[t] = -1\n",
    "\n",
    "        return (count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        count = defaultdict(int)\n",
    "        ans = 0\n",
    "        for tm in time:\n",
    "            group = tm % 60\n",
    "            ans += count[60-group]\n",
    "            ans += count[-group]\n",
    "            count[group] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        for i in range(len(time)):\n",
    "            time[i] = time[i]%60\n",
    "        num = Counter(time)\n",
    "        out = 0\n",
    "        for i in range(1,30):\n",
    "            out = out + num[i]*num[60-i]\n",
    "        out = out + int(num[0]*(num[0]-1)/2)\n",
    "        out = out + int(num[30]*(num[30]-1)/2)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        nums = [0] * 60\n",
    "        for i in range(len(time)):\n",
    "            time[i] %= 60\n",
    "            nums[time[i]] +=1\n",
    "        cnt = 0\n",
    "        for i in range(60):\n",
    "            if i == (60-i)%60:\n",
    "                cnt += nums[i] * (nums[i]-1)\n",
    "            else:\n",
    "                cnt += nums[i]*nums[60-i]\n",
    "\n",
    "        return cnt // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        cnt = [0] * 60\n",
    "        for t in time:\n",
    "            cnt[t % 60] += 1\n",
    "        res = 0\n",
    "        for i in range(1, 30):\n",
    "            res += cnt[i] * cnt[60 - i]\n",
    "        res += cnt[0] * (cnt[0] - 1) // 2 + cnt[30] * (cnt[30] - 1) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        bf = [0]*60\n",
    "        ans = 0\n",
    "        for num in time:\n",
    "            x = num % 60\n",
    "            if bf[(60-x)%60]:\n",
    "                ans+=bf[(60-x)%60]\n",
    "            bf[x]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPairsDivisibleBy60(self, time: List[int]) -> int:\n",
    "        cnt = [0] * 60\n",
    "        for t in time:\n",
    "            cnt[t % 60] += 1\n",
    "        res = 0\n",
    "        for i in range(1, 30):\n",
    "            res += cnt[i] * cnt[60 - i]\n",
    "        res += cnt[0] * (cnt[0] - 1) // 2 + cnt[30] * (cnt[30] - 1) // 2\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
